Data Structure
Big O Notation Q and A
Explain Big O notation.
Answer:Big O notation is a way to describe the efficiency or scalability of an algorithm. It tells us how the runtime or memory usage of an algorithm grows as the input size increases. Big O describes worst-case growth rate. It is important as it helps to :
- Helps compare different algorithms.
- Predicts how an algorithm will perform with large inputs.
- Allows us to optimize code for efficiency.
What are the commom Big O Complexities?
Answer:
O(1): Constant Time
The algorithm takes the same amount of time, no matter the input size.
Example: Accessing an array element by index.
O(log n): Logarithmic Time
The runtime grows logarithmically as input increases.
Example: Binary search (divides the problem in half each time).
O(n) : Linear Time
Runtime grows proportionally with input size.
Example: Looping through an array.
O(n log n) : Linearithmic Time
Common in efficient sorting algorithms (e.g., Merge Sort, QuickSort).
Example: Sorting a list.
O(n2): Quadratic Time
Runtime grows with the square of input size.
Example: Nested loops (e.g., Bubble Sort).
O(2n) : Exponential Time
Runtime doubles with each additional input (very slow).
Example: Recursive Fibonacci (without memoization).
O(n!) : Factorial Time
Runtime grows factorially (extremely slow).
Example: Brute-force solutions like the Traveling Salesman Problem.
How to determine Big O notation?
Answer: To determine Big O notation follow given steps:
Ignore constants (e.g., O(2n) --> O(n)).
Keep the dominant term (e.g., O(n2 + n) --> O(n2)).
Different inputs --> different variables (e.g., two arrays --> O(a + b)).